package TreeFormula;

import stack.Stack;

/**
 *
 * Exercise 9 (Part 2)
 * @author Katrin Baryshnikova
 */
public class PostfixNotation {

    /**
     * Преобразует входную последовательность из инфиксной формы в постфиксную
     * @param s  входная последовательность
     * @return  
     */
    public static String convertInToPrefix(String s) {
        // создаем строку с ответом
        String answer = new String();
        // длина входной строки
        int n = s.length();
        // создаем стек из символов
        Stack<Character> st = new Stack<Character>(n);
        Character symb;
        for (int i = 0; i < n; i++) {
            symb = s.charAt(i); // получаем i-ый символ из строки и обрабатываем
            // если он число или буква 
            if (isDigit(symb) || isSymbol(symb)) {
                answer += symb; // добавляем его в ответ
                answer += ' ';
            } else if (isOpenScope(symb)) { //если открывающая скобка
                st.push(symb);  // кладем в стек
            } else if (isCloseScope(symb)) { // если закрывающая скобка
                // пока стек не пустой и на его вершине не лежит открывающая скобка
                while (!st.isEmpty() && st.peek() != '(') {
                    // добавляем к ответу элементы с вершины стека
                    answer += st.pop();
                    answer += ' ';
                }
                // выталкиваем открывающую скобку
                st.pop();
            } else if (isOperation(symb)) { // если операция
                // пока стек не пуст и приоритет этой операции не больше 
                // приоритета операции с вершины стека 
                while (!st.isEmpty() && prior(symb) <= prior(st.peek())) {
                    // добавляем к ответу элементы с вершины стека
                    answer += st.pop();
                    answer += ' ';
                }
                // добавляем в стек текущую операцию
                st.push(symb);
            }
        }
        // по завершению добавляем в ответ все что осталось в стеке
        while (!st.isEmpty()) {
            answer += st.pop();
        }
        return answer;
    }

    /**
     * Проверяет является ли символ буквой
     * @param c - символ
     * @return true - если c буква
     */
    private static boolean isSymbol(Character c) {
        return (int) c <= 122 && (int) c >= 97 ? true : false;
    }

    /**
     * Проверяет является ли символ числом
     * @param c - символ
     * @return true - если c число
     */
    private static boolean isDigit(Character c) {
        return (int) c <= 57 && (int) c >= 48 ? true : false;
    }

    /**
     * Проверяет является ли символ операцией
     * @param c - символ
     * @return true - если c опреация
     */
    private static boolean isOperation(Character c) {
        int a = (int) c;
        return a == 43 || a == 45 || a == 47 || a == 42 ? true : false;
    }

    /**
     * Проверяет является ли символ открывающейся скобкой
     * @param c - символ
     * @return true - если c открывающаяся скобка
     */
    private static boolean isOpenScope(Character c) {
        return (int) c == 40 ? true : false;
    }

    /**
     * Проверяет является ли символ закрывающейся скобкой
     * @param c - символ
     * @return true - если c закрывающаяся скобка
     */
    private static boolean isCloseScope(Character c) {
        return (int) c == 41 ? true : false;
    }

    /**
     * Возвращает приоритет опреаций
     * @param c - символ
     * @return если c равен '/' или '*' возвращает 2,
     *  если c равен '+' или '-' возвращает 1
     */
    private static int prior(Character c) {
        switch (c) {
            case '/':
            case '*':
                return 2;
            case '+':
            case '-':
                return 1;
            default:
                return 0;
        }
    }
}
